package com.da.javatest.niuke.baodian;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author chenlida
 * @date 2020/10/10 11:17
 * https://www.nowcoder.com/practice/8380c8cf28954a188362206b1991b5d6?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C45Permutation {
    public ArrayList<String> getPermutation(String A) {
        ArrayList<String> list = new ArrayList<>();
        permutation(list, A.toCharArray(), 0);
        Collections.sort(list);
        Collections.reverse(list);
        return list;
    }

    public static void permutation(ArrayList<String> list, char[] array, int k) {
        if (k == array.length) {
            list.add(new String(array));
            return;
        }
        for (int i = k; i < array.length; i++) {
            // 交换
            swap(array, i, k);
            permutation(list, array, k + 1);
            // 还原
            swap(array, i, k);
        }
    }

    public static void swap(char[] array, int i, int j) {
        if (i != j) {
            char temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    public static void main(String[] args) {
        C45Permutation test = new C45Permutation();
        System.out.println(test.getPermutation("ABCD"));
    }

}
